package leetCode.solution;

public class Solution55 {

	public static void main(String[] args) {
		
	}
	public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n == 1)return true;
        for(int i = n - 2; i >= 0; i--){
            if(nums[i] == 0){
                int j = i - 1;
                for(; j >= 0; j--){
                    if(nums[j] > i - j) {
                    	i=j;
                    	break;
                    }
                }
                if(j < 0)return false;
            }
        }
        return true;
    }
	
	public boolean canJump2(int[] nums) {
        if (nums.length == 1 ) return true;
        for (int i= nums.length -2;i>=0;i--){
            if (nums[i] ==0){
                i--;
                for (int j = 1;i>=0;i--,j++){
                    if (nums[i] > j) break;
                }
                if (i<0) return false;
            }
        }
        return true;
    }
	
	 public boolean canJump3(int[] nums) {
	        int n = nums.length;
	        int rightmost = 0;
	        for (int i = 0; i < n; ++i) {
	            if (i <= rightmost) {
	                rightmost = Math.max(rightmost, i + nums[i]);
	                if (rightmost >= n - 1) {
	                    return true;
	                }
	            }
	        }
	        return false;
	    }

}
